package LeetCode.题库.简单;

import org.junit.Test;
import 题组.Solution;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 10 - 9:02
 * @Description 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
 * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔
 * @Version 简单
 */
public class _589N叉树的前序遍历 {
    static Integer[] values = {1,null,3,2,4,null,5,6};
    static NTreeNode treeRoot;
    static {
        treeRoot = new NTreeNode(values[0]);
        NTreeNode n3 = new NTreeNode(3);
        n3.children = new ArrayList<>();
        n3.children.add(new NTreeNode(5));
        n3.children.add(new NTreeNode(6));

        treeRoot.children = new ArrayList<>();
        treeRoot.children.add(new NTreeNode(3));
        treeRoot.children.add(new NTreeNode(2));
        treeRoot.children.add(new NTreeNode(4));
    }
    /*
                1
           3    2    4
         5   6

         输出：1,3,5,6,2,4
     */


    @Test
    public void solve(){
        List<Integer> res = preorder(treeRoot);
        System.out.println(res);
    }
    /*by me 递归*/
    public List<Integer> preorder(NTreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        proceed(root, res);
        return res;
    }

    public void proceed(NTreeNode root, List<Integer> list){
        if(root == null)
            return;
        //添加根
        list.add(root.val);
        //添加子节点
        for(NTreeNode node:root.children){
            proceed(node, list);
        }
    }
    /*官方思路*/
    //迭代
    public List<Integer> preorder1(NTreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<NTreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            NTreeNode node = stack.pop();
            res.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; --i) {
                stack.push(node.children.get(i));
            }
        }
        return res;
    }

}
